#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

int threshold;

void shiftdown(int R[], int n, int i) {
    while (i <= n / 2) {
        int maxchd = 2 * i;
        if (maxchd + 1 <= n && R[maxchd] < R[maxchd + 1]) maxchd++;
        if (R[i] >= R[maxchd]) return;
        swap(R[i], R[maxchd]);
        i = maxchd;
    }
}

void BuildHeap(int R[], int n) {
    for (int i = n / 2; i >= 1; i--) {
        shiftdown(R, n, i);
    }
}

void heapsort(int R[], int n) {
    BuildHeap(R, n);
    cout << "Heap:";
    for (int i = 1; i <= n; i++) cout << R[i] << " ";
    cout << endl;

    for (int i = n; i > 1; i--) {
        swap(R[1], R[i]);
        shiftdown(R, i - 1, 1);
    }
}
void quicksort(int* R, int m, int n, int dep, int nn) {
    
    while (n - m + 1 > threshold) {
         if (dep >=nn) {
            heapsort(&R[m-1], n - m + 1);
            return;
        }
        int mid = (m + n) / 2;
    swap(R[mid],R[m+1]);
    if (R[n] < R[m+1]) swap(R[n], R[m+1]);
    if (R[m] > R[n]) swap(R[m], R[n]);
    if (R[m+1] > R[m]) swap(R[m+1], R[m]);
// 将中位数放到开头
    int K = R[m];
    int i = m, j = m, k = n;
    // 三路分划
    while (j <= k) {
        if (R[j] < K) {
            swap(R[i], R[j]);
            i++;
            j++;
        } else if (R[j] > K) {
            swap(R[j], R[k]);
            k--;
        } else {
            j++;
        }
    }
       
      
     
        // 优先处理较短的区间
        if (i - m < n - k) {
            quicksort(R, m,i-1, dep + 1, nn);  // 处理左区间
            m = k + 1;  // 处理右区间
        } else {
            quicksort(R, k+1, n, dep + 1, nn);  // 处理右区间
            n = i- 1;  // 处理左区间
        }
        dep++;
    }
}

void InsertionSort(int R[], int n) {
    for (int i = 2; i <= n; i++) {
        int K = R[i], j = i - 1;
        while (j >= 1 && R[j] > K) {
            R[j + 1] = R[j];
            j--;
        }
        R[j + 1] = K;
    }
}

void sort(int* R, int n) {
    cout << "depth_limit:" << (int)(2 * log(n) / log(2)) << endl;
    quicksort(R, 1, n, 0, (int)(2 * log(n) / log(2)));
    cout << "Intermediate:";
    for (int i = 1; i <= n; i++) {
        cout << R[i] << " ";
    }
    cout << endl;

    InsertionSort(R, n);
}

int main()
{
    int n,i;
    int a[50010];
    scanf("%d %d", &n, &threshold);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    sort(a,n);
    
    printf("Final:");
    for (i = 1; i <= n; i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

